package com.zhangxiaofanfan.hotcode.fourth.third;

/**
 * <a href="https://leetcode.cn/problems/edit-distance/description/?envType=study-plan-v2&envId=top-100-liked">72. 编辑距离</a>
 *
 * @date 2024-07-13 03:14:13
 * @author zhangxiaofanfan
 */
public class HotCode095 {
    public static void main(String[] args) {
        HotCode095 hotCode = new HotCode095();
        System.out.println(hotCode.minDistance("horse", "ros"));
    }

    public int minDistance(String word1, String word2) {
        if (word1.isEmpty()) {
            return word2.length();
        }
        if (word2.isEmpty()) {
            return word1.length();
        }
        int[][] dp = new int[word1.length() + 1][word2.length() + 1];
        for (int index1 = 1, index2; index1 <= word1.length(); index1++) {
            for (index2 = 1; index2 <= word2.length(); index2++) {
                if (word1.charAt(index1 - 1) == word2.charAt(index2 - 1)) {
                    dp[index1][index2] = Math.max(Math.min(dp[index1 - 1][index2], dp[index1][index2 - 1]), dp[index1 - 1][index2 - 1]);
                } else {
                    dp[index1][index2] = Math.max(Math.min(dp[index1 - 1][index2], dp[index1][index2 - 1]), dp[index1 - 1][index2 - 1]) + 1;
                }
            }
        }
        return dp[word1.length()][word2.length()];
    }
}